學習紀錄 I

學習紀錄 $\rm I$

$\rm Merge Sort$

分為二個步驟

• 拆分
  • 把大陣列切一半成為兩個小陣列
  • 把切好的兩個小陣列再各自切一半
  • 重複上一動直到每個小陣列都只剩一個元素
• 合併
  • 排序兩個只剩一個元素的小陣列並合併
  • 把兩邊排序好的小陣列合併並排序成一個陣列
  • 重複步驟二直到所有小陣列都合併成一個大陣列

時間估算

設 $T(n)$ 是 $n$ 個數的 $\rm list$ 用 $\rm Merge sort$ 所須時間
$\rm Merge sort$ 的作法是把兩個 $\rm lists$ (各有 $\frac{n}{2}$ 個排好的數) 合併得到答案
因此, $T(n)$ 含合併的時間, 以及必須先把兩個　$\rm lists$ 排好要花的時間
合併的時間是線性的 $O(n)$ 時間
有 $\frac{n}{2}$ 個數的 $\rm list$ 要排好, 使用 $\rm Merge sort$ (遞迴) 要 $T(\frac{n}{2})$ 時間
因此, 共花 $O(n) + 2T(\frac{n}{2})$
即　$\rm T(n)=2T(\frac{n}{2})+O(n)$

複雜度證明

$\rm T(n)=2T(\frac{n}{2})+O(n)$
將 $\rm O(n)$ 視為 $\rm cn$ ， $\rm c$ 為常數
$\rm T(n)=2T(\frac{n}{2})+cn$
$\rm T(\frac{n}{2}) = 2T(\frac{n}{4}) + c(\frac{n}{2})$
$\rm T(n)=2\left( 2T(\frac{n}{4}) + c(\frac{n}{2}) \right)+cn$
$\rm T(n) = 4T(n/4) + 2cn$
重複該步驟 $\rm k$ 次 可得
$\rm T(n) = 2^kT(\frac{n}{2^k}) + kcn$
假設 $\rm n = 2^k$ ， $\rm k = \log_2(n)$ 可得
$\rm T(n) = nT(1) + cn\log_2(n)$
$\rm T(1)$ 的時間為 $\rm 1$
$\rm cn\log_2(n)$ 時間為 $\rm O(n\log_2(n))$
也就是
$\rm T(n) = O(n) + O(n\log_2(n))$
$\rm Merge Sort$ 的複雜度將$\rm bound$在 $\rm O(n\log_2(n))$